struct Primes(Vec<usize>);
impl Primes {
    fn new() -> Primes {
        Primes(vec![2, 3, 5, 7])
    }
    fn expand(&mut self, max: usize) {
        let min = self.0[self.0.len() - 1] + 1;
        'root: for x in min..=max {
            for i in self.0.iter() {
                if x % i == 0 {
                    continue 'root;
                }
                if i.pow(2) > x {
                    break;
                }
            }
            self.0.push(x);
        }
    }
    fn contain(&self, num: usize) -> bool {
        let (mut l, mut c, mut r) = (0, self.0.len() / 2, self.0.len());
        while self.0[c] != num {
            if l == c {
                return false;
            }
            if self.0[c] > num {
                r = c;
            } else {
                l = c;
            }
            c = (l + r) / 2;
        }
        true
    }
}

/// [Distinct primes factors](https://projecteuler.net/problem=47)
fn main() {
    let mut primes = Primes::new();
    println!("{}", distinct_primes(4, &mut primes));
}

fn distinct_primes(n: usize, primes: &mut Primes) -> usize {
    let mut x = 4;
    'root: loop {
        primes.expand(x);
        if primes.contain(x) || get_number_distinct_prime_factors(x, primes) != n {
            x += 1;
            continue;
        }
        let mut y = x;
        for _ in 1..n {
            y += 1;
            if get_number_distinct_prime_factors(y, primes) != n {
                break;
            }
            if y + 1 == x + n {
                break 'root;
            }
        }
        x = y + 1;
    }
    x
}

fn get_number_distinct_prime_factors(n: usize, primes: &mut Primes) -> usize {
    primes.expand(n);
    let mut count = 0;
    let mut m = n;
    for i in primes.0.iter() {
        if *i > m {
            break;
        }
        if m % i == 0 {
            count += 1;
            m = m / i;
            while m % i == 0 {
                m = m / i;
            }
        }
    }
    count
}

#[cfg(test)]
mod test {
    use super::*;
    #[test]
    fn get_number() {
        let mut primes = Primes::new();
        assert_eq!(get_number_distinct_prime_factors(1, &mut primes), 0);
        assert_eq!(get_number_distinct_prime_factors(2, &mut primes), 0);
        assert_eq!(get_number_distinct_prime_factors(3, &mut primes), 0);
        assert_eq!(get_number_distinct_prime_factors(4, &mut primes), 1);
        assert_eq!(get_number_distinct_prime_factors(8, &mut primes), 1);
        assert_eq!(get_number_distinct_prime_factors(14, &mut primes), 2);
        assert_eq!(get_number_distinct_prime_factors(15, &mut primes), 2);
    }
    #[test]
    fn get_distinct() {
        let mut primes = Primes::new();
        assert_eq!(distinct_primes(2, &mut primes), 14);
        assert_eq!(distinct_primes(3, &mut primes), 644);
    }
}
